#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include "Q.h"

typedef int BTDataType;

typedef struct BinaryTree
{
	BTDataType data;
	struct BinaryTree* left;
	struct BinaryTree* right;

}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* buy = (BTNode*)malloc(sizeof(BTNode));
	buy->data = x;
	buy->left = NULL;
	buy->right = NULL;
	return buy;
}

BTNode* CreateNode()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	//BTNode* node7 = BuyNode(7);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	//node5->left = node7;
	return node1;
}

void PrevOrder(BTNode* BT)
{
	if (BT == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", BT->data);
	PrevOrder(BT->left);
	PrevOrder(BT->right);
}

void InOrder(BTNode* BT)
{
	if (BT == NULL)
	{
		printf("NULL ");
		return;
	}

	PrevOrder(BT->left);
	printf("%d ", BT->data);
	PrevOrder(BT->right);
}

void PostOrder(BTNode* BT)
{
	if (BT == NULL)
	{
		printf("NULL ");
		return;
	}

	PrevOrder(BT->left);

	PrevOrder(BT->right);
	printf("%d ", BT->data);
}

int BTSize(BTNode* BT)
{
	return BT == NULL ? 0 : BTSize(BT->left) + BTSize(BT->right) + 1;
}

int BTLeafSize(BTNode* BT)
{
	if (BT == NULL)
	{
		return 0 ;
	}
	if (BT->left == NULL && BT->right == NULL)
	{
		return 1;
	}
	return BTLeafSize(BT->left) + BTLeafSize(BT->right);
}

int BTHeight(BTNode* BT)
{
	if (BT == NULL)
	{
		return 0;
	}
	int lh = BTHeight(BT->left);
	int rh = BTHeight(BT->right);
	return lh > rh ? lh + 1 : rh + 1;
}

int BTLevalSize(BTNode* BT, int k)
{
	if (BT == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTLevalSize(BT->left, k - 1) + BTLevalSize(BT->right, k - 1);
}

BTNode* BTFind(BTNode* BT, BTDataType x)
{
	if (BT == NULL)
	{
		return NULL;
	}
	if (BT->data == x)
	{
		return BT;
	}

	BTNode* left = BTFind(BT->left, x);

	if (left)
		return left;
	BTNode* right = BTFind(BT->right, x);
	if (right)
		return right;
	return NULL;
}
void LevalOrder(BTNode* BT)
{
	Queue q;
	QInit(&q);
	if (BT)
		QPush(&q, BT);
	while (!QEmpty(&q))
	{
		BTNode* root = QFront(&q);
		QPop(&q);
		printf("%d ", root->data);
		if (root->left)
			QPush(&q, root->left);
		if (root->right)
			QPush(&q, root->right);
	}
	QDestory(&q);
}
void BTDestory(BTNode* BT)
{
	if (BT==NULL)
		return;
	BTDestory(BT->left);
	BTDestory(BT->right);
	free(BT);
}
bool BTComplete(BTNode* BT)
{
	Queue q;
	QInit(&q);
	QPush(&q, BT);
	while (!QEmpty(&q))
	{
		BTNode* root = QFront(&q);
		QPop(&q);
		if (root == NULL)
			break;
		QPush(&q, root->left);
		QPush(&q, root->right);
	}
	while (!QEmpty(&q))
	{
		BTNode* root = QFront(&q);
		QPop(&q);
		if (root != NULL)
			return false;
	}
	return true;
}
int main()
{
	BTNode* BT = CreateNode();
	//BTDestory(BT);
	//BT = NULL;
	PrevOrder(BT);
	printf("\n");
	InOrder(BT);
	printf("\n");
	PostOrder(BT);
	printf("\n");
	printf("%d ",BTSize(BT));
	printf("%d ", BTLeafSize(BT));
	printf("%d ", BTHeight(BT));
	printf("%d ", BTLevalSize(BT,3));
	printf("%d \n", BTFind(BT, 6)->data);
	printf("%d \n", BTComplete(BT));
	LevalOrder(BT);

	return 0;
}